package stack;

/**
 * 链式栈
 * 
 * @author wt
 *
 * @param <T>
 */
public class LinkedStack<T> implements SStack<T> {
	private Node<T> top; // 栈顶结点

	/**
	 * 构造空栈
	 */
	public LinkedStack() {
		// 带头结点的链式栈,栈顶指针指向头结点
		this.top = new Node<T>(null, null);
	}

	/**
	 * 判断栈是否为空
	 * 
	 */
	public boolean isEmpty() {
		return this.top.next == null;
	}

	/**
	 * 元素x入栈，空对象不能入栈
	 * 
	 */
	public void push(T x) {
		if (x != null) {  // 在栈顶查找,x结点作为新的栈顶结点
			this.top.next = new Node(x, this.top.next);
		}
	}

	@Override
	public boolean isFull() {
		return false;
	}

	/**
	 * 出栈，返回栈顶元素，若栈空返回null
	 */
	public T pop() {
		if (this.top.next == null) {
			return null;
		}
		T temp = this.top.next.data; // 取栈顶结点元素
		this.top.next = this.top.next.next; // 删除栈顶结点
		return temp;
	}

	/**
	 * 取栈顶元素，未出栈，若栈空返回null
	 */
	public T getTop() {
		return this.top.next == null ? null : this.top.next.data;
	}

	/**
	 * 返回栈所有元素的描述字符串，形式为“(,)”。算法同不带头结点的单链表
	 */
	public String toString() {
		System.out.print("当前链式栈内元素为:");
		String str = "(";
		for (Node<T> p = this.top.next; p != null; p = p.next) {
			str += p.data.toString();
			if (p.next != null)
				str += ", "; // 不是最后一个结点时后加分隔符
		}
		System.out.println(str + ")");
		return str + ")"; // 空表返回()
	}
}
